// Copyright 2024 Tvux
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//      http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

package _135

func candy(ratings []int) int {
	candies := make([]int, len(ratings))
	for i := range candies {
		candies[i] = 1 // 先保证每个人至少一个糖果
	}
	// 先从左往右遍历，从下标1开始
	// 如果当前元素比前一个元素的评分高，那么当前元素对应的糖果就在前面元素对应的糖果的基础上+1
	for i := 1; i < len(ratings); i++ {
		if ratings[i] > ratings[i-1] {
			candies[i] = candies[i-1] + 1
		}
	}
	// 再从右往左遍历，从下标n-2开始
	// 如果当前元素比后一个元素的评分高，并且当前元素对应的糖果的个数是小于等于后一个元素对应的糖果的
	// 就在后一个元素对应的糖果基础上+1
	for i := len(candies) - 2; i >= 0; i-- {
		if ratings[i] > ratings[i+1] && candies[i] <= candies[i+1] {
			candies[i] = candies[i+1] + 1
		}
	}
	res := 0
	for _, num := range candies {
		res += num
	}
	return res
}
